package com.hanxiaozhang.no3algorithm;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 〈一句话功能简述〉<br>
 * 〈例题1〉
 *  java 无序数组中，找出两个元素相加等于N的所有组合？ o（n）
 *
 * @author hanxinghua
 * @create 2020/4/10
 * @since 1.0.0
 */
public class No1Example {

    public static void main(String[] args) {
        //初始化数组
        int[] table ={1,3,13,33,43,47,16,44,32,10};
        int[] table1 ={8,3,5,78,19,47,16,44,32,10,34,565,99,88,12,50};

        //方式1
//        method1(table, 101);

        //方式2
//        method2(table, 92);

        //方式3
        method3(table1,100);

    }

    /**
     * 最笨的方法：时间复杂度是o（n2）
     * 思路：第一循环找出第一个数；第二循环找出来第二个数，
     *      如果"第一个数+第二个数=N" 输出结果
     *
     * @param table
     * @param n
     */
    private static void method1(int[] table, int n) {
        int size = table.length;
        for (int i = 0; i <size ; i++) {
            int temp=table[i];
            //注意：int j = i，不是int j = 0（有重复）
            for (int j = i; j <size ; j++) {
                if(n==(temp+table[j])){
                    System.out.println(n+" = "+table[j]+" + "+temp);
                }
            }
        }
    }


    /**
     * 简单的方法：（理想情况下（无hash碰撞）可以：使用有限）
     * 思路：声明一个数组，使用hash原理（元素的值%数组长度=元素的在数组中位置）存储各元素是否存在的标志，
     *      即0：无，1：有。然后遍历数组，判断N与当前数组元素的差值在数组中是否存在,存在证明有该数。
     * 解析：该算法不要求数组有序，但要求一个hash数组的额外空间，时间复杂度是O(n)，
     *     并且要求元素去重后hash的没有碰撞(这个元素有两类：一是第一个数，即所有元素在新定义的数组中不会发生碰撞；
     *     二是（N-第一个数）的未知数，这个未知数在新定义的数组中不会发生碰撞)
     * 如何保证元素去重后hash无碰撞？合理设置数组的长度，长度是无序数组所有元素+N数中最大的值
     *
     * @param table
     * @param n
     */
    private static void method2(int[] table, int n) {
        //数组的长度
        int tableSize = table.length;
        //hash数组的长度，
        int hashSize=92;
        //声明一个hash数组
        int[] hash = new int[hashSize];
        for(int i = 0; i < tableSize; i++) {
            //hash表存储数组各元素是否存在的标志
            hash[table[i]%hashSize] = 1;
        }
        System.out.println("hash数组:"+Arrays.toString(hash));

        for(int i = 0; i < tableSize; i++) {
            int temp = n - table[i];
            if((temp >= table[i]) && (hash[temp%hashSize] == 1)){
                System.out.println(n+" = "+table[i]+" + "+temp);
            }
        }
    }


    /**
     * 问题：会出现：
     * 100 = 88 + 12
     * 100 = 12 + 88
     * 使用LinkedHashMap插入元素有顺序，然后判断顺序
     *
     *
     * @param table
     * @param n
     */
    private static void method3(int[] table, int n) {
        // key：数值，value：数值对应的个数
        HashMap<Integer, Integer> map = new LinkedHashMap<>();
        //数组的长度
        int tableSize = table.length;
        //存储数据
        for(int i = 0; i < tableSize; i++) {
            int temp = table[i];
            int count = 0;
            if (map.containsKey(table[i]))
            {
                count = map.get(temp);
            }
            map.put(temp, count + 1);
        }
        AtomicInteger count= new AtomicInteger();

        map.forEach((key, value)->{
            int temp =n-key;
            if(map.containsKey(temp)){
                //去除key与temp值相同，但是数组中只有一个值得情况
                if(!(n ==temp<<1 && map.get(temp) == 1)){
                    System.out.println("第一个元素位置："+count);
                    System.out.println(n+" = "+key+" + "+temp);
                }
            }
            count.getAndIncrement();
        });


    }


}

